home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / cool / ge_cool.lha / GE_COOL2.1 / src / Tree / Binary_Tree.C < prev    next >
C/C++ Source or Header  |  1992-06-29  |  14KB  |  369 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12.  
  13.  
  14. #include <cool/Binary_Tree.h>
  15.  
  16. // CoolBinary_Tree -- Simple constructor to initialize a CoolBinary_Tree object
  17. // Input:         None
  18. // Output:        None
  19.  
  20. template <class Type>
  21. CoolBinary_Tree<Type>::CoolBinary_Tree<Type> () {
  22.   this->compare = &Type##_default_node_compare; // Pointer to compare function
  23. }
  24.  
  25.  
  26.  
  27. // CoolBinary_Tree -- constructor to initialize a CoolBinary_Tree object to have the
  28. //                same size and values as some other CoolBinary_Tree object
  29. // Input:         Reference to CoolBinary_Tree
  30. // Output:        None
  31.  
  32. template <class Type>
  33. CoolBinary_Tree<Type>::CoolBinary_Tree<Type> (const CoolBinary_Tree<Type>& b)
  34. {
  35.   this->compare = b.compare;            // Pointer to compare function
  36.   this->number_nodes = b.number_nodes;
  37.   this->root = this->copy_nodes (b.get_root());
  38.   this->current_position () = b.current_position ();
  39. }
  40.  
  41.  
  42.  
  43. // ~CoolBinary_Tree -- Destructor for the CoolBinary_Tree class
  44. // Input:          None
  45. // Output:         None
  46.  
  47. template <class Type>
  48. CoolBinary_Tree<Type>::~CoolBinary_Tree<Type> () {
  49.   delete this->root;                // Virtual destructor called recurs.
  50. }                        // on all nodes 
  51.  
  52. // value -- Return value of node at current position
  53. // Input:   None
  54. // Output:  Reference to value of node at current position
  55.  
  56. template <class Type>
  57. Type& CoolBinary_Tree<Type>::value () {
  58. #if ERROR_CHECKING
  59.  if (this->state.stack.is_empty() )             // If invalid current position
  60.    this->curpos_error (#Type, "value()");    // Raise exception
  61. #endif
  62.   Stack_Entry stack_entry = this->state.stack.top(); // get top stack
  63.   return (((CoolBinary_Node<Type>*)stack_entry.get_first())->get()); // Return value
  64. }
  65.  
  66.  
  67. template <class Type>
  68. Boolean CoolBinary_Tree<Type>::put_internal
  69.                             (const Type& value, Boolean avl) {
  70.  
  71.   if (this->root == NULL) {            // If this is the first node
  72.     this->root = new CoolBinary_Node<Type> (value);    // Add new node and value
  73.     this->number_nodes++;            // Update node count
  74.     return TRUE;                // Indicate success
  75.   }
  76.   CoolBinary_Node<Type>* ptr = (CoolBinary_Node<Type>*)this->root; // Start at root
  77.   BT_Stack stack;                // Stack for AVL balancing
  78.   while (TRUE) {                // Until we find location
  79.     int pos = (*this->compare)(ptr->get(),value); // Compare data values
  80.     if (pos == 0)                 // If data value exists in tree
  81.       return FALSE;                //    indicate node not added
  82.     else if (pos > 0) {                // Data down left subtree?
  83.       if (avl)
  84.     stack.push (Stack_Entry ((CoolBinary_Node*)ptr,LEFT)); // Push parent
  85.       if (ptr->get_ltree() == NULL) {        // If at leaf node
  86.     ptr->set_ltree ((new CoolBinary_Node<Type> (value))); // Add node to ltree
  87.     this->number_nodes++;            // Update node count
  88.     break;                    // Break out of loop and exit
  89.       }
  90.       else {
  91.     ptr = ptr->get_ltree();            // Else point to left subtree
  92.     continue;                // And continue search
  93.       }
  94.     }
  95.     else {                    // Else down right subtree
  96.       if (avl)
  97.     stack.push (Stack_Entry ((CoolBinary_Node*)ptr,RIGHT)); // Push on stack
  98.       if (ptr->get_rtree() == NULL) {        // If at leaf node
  99.     ptr->set_rtree ((new CoolBinary_Node<Type> (value))); // Add node to rtree
  100.     this->number_nodes++;                // Update node count
  101.     break;                    // Break out of loop and exit
  102.       }
  103.       else {
  104.     ptr = ptr->get_rtree();            // Grab right subtree dir
  105.     continue;                // And continue to search;
  106.       }
  107.     }
  108.   }
  109.   if (avl)                    // Balance it if an AVL tree
  110.     CoolBinary_Tree::avl_put_balance (stack);
  111.  
  112.   this->reset();                // Invalidate current position
  113.   return TRUE;                    // Return success
  114. }
  115.  
  116.  
  117. // remove_internal -- does the actual work of removing a value from bin tree
  118. //                    for avl trees, will make call to check avl balance
  119. // Input:          -- value to remove + optional Boolean for AVL trees
  120. // output          -- TRUE if item sucessfully removed. FALSE otherwise.
  121. template <class Type>
  122. Boolean CoolBinary_Tree<Type>::remove_internal
  123.                            (const Type& value, Boolean avl) {
  124.   if (this->root == NULL)            // If there are no nodes
  125.     return FALSE;                // indicate failure
  126.   BT_Stack stack1;                // Allocate traversal stack
  127.   Left_Right route = NONE;            // Last subtree taken
  128.   CoolBinary_Node<Type> *ptr = (CoolBinary_Node<Type>*)this->root; // Start at root
  129.   CoolBinary_Node<Type> *parent_ptr = NULL;        // Save pointer to parent
  130.   CoolBinary_Node<Type> *ptr1, *ptr2;        // temp ptrs to nodes
  131.   while (TRUE) {                // Until we find location
  132.     int pos = (*this->compare)(ptr->get(),value); // Compare data values
  133.     if (pos == 0) {                // If node to delete is found
  134.       if (ptr->get_rtree() == NULL) {        // If no right subtree
  135.     if (route == LEFT)            // If child of parent's ltree
  136.       parent_ptr->set_ltree(ptr->get_ltree()); // Set to left subtree
  137.     else if (route == RIGHT)
  138.       parent_ptr->set_rtree(ptr->get_ltree()); // Set to right subtree
  139.     else this->root = ptr->get_ltree();    // Make ltree the new root
  140.       }
  141.       else if (ptr->get_ltree() == NULL) {    // Else if no left subtree
  142.     if (route == LEFT)            // If child of parent ltree
  143.       parent_ptr->set_ltree(ptr->get_rtree()); // Set to left subtree
  144.     else if (route == RIGHT)
  145.       parent_ptr->set_rtree(ptr->get_rtree()); // Set to right subtree
  146.     else this->root = ptr->get_rtree();       //    rtree is the new root.
  147.       }
  148.   
  149.       // Node(a) with value to be deleted has both a left and right subtree.
  150.       // We need to look for the node(b) with the next smallest value and
  151.       // copy it's value into node(a). Then adjust the parent of node(b) 
  152.       // to point at node(b)'s left subtree (right subtree will always be 
  153.       // NULL).  ptr is left pointing at node(b) so it is the
  154.       // one which is eventually deleted.
  155.       else {
  156.     if (avl)                 // for avl trees
  157.       stack1.push (Stack_Entry((CoolBinary_Node*)ptr,LEFT)); // push on stack
  158.         ptr1 = ptr;                // Save node with matched data
  159.     ptr2 = ptr1;                // last parent initially ptr
  160.     ptr = ptr->get_ltree();            // Start with node's ltree
  161.     while (ptr->get_rtree() != NULL) {    // Follow rtree til null rtree
  162.       if (avl)                 // for avl trees
  163.         stack1.push (Stack_Entry((CoolBinary_Node*)ptr,RIGHT)); // push on stack
  164.       ptr2 = ptr;                // save last parent
  165.       ptr = ptr->get_rtree();        // get right subtree
  166.     }
  167.     ptr1->set (ptr->get());            // Move next smallest value up
  168.     if (ptr1 == ptr2)             // ltree had no rtrees
  169.       ptr2->set_ltree (ptr->get_ltree());    // Del node is parents ltree
  170.     else 
  171.       ptr2->set_rtree (ptr->get_ltree());    // Del node is parents rtree
  172.       }
  173.  
  174.       // DELETE the node ptr points at
  175.       this->number_nodes--;            // Decrement node count
  176.       if (this->number_nodes == 0)         // If no more nodes in tree
  177.     this->root = NULL;            // Nullify root pointer
  178.       ptr->set_ltree (NULL);            // Nullify left subtree pointer
  179.       ptr->set_rtree (NULL);            // Nullify right subtree pointer
  180.       delete ptr;                // Deallocate memory
  181.       this->reset();                // Invalidate current position<
  182.       break;                    // exit loop
  183.     }
  184.     else if (pos > 0) {                // Data down left subtree?
  185.       if (ptr->get_ltree() == NULL) {        // If at leaf node
  186.     return FALSE;                // Indicate node not found
  187.       }
  188.       else {
  189.     if (avl)                 // if avl tree
  190.       stack1.push (Stack_Entry((CoolBinary_Node*)ptr,LEFT)); // push on stack1
  191.     parent_ptr = ptr;            // Save parent pointer
  192.     route = LEFT;                // Save route taken
  193.     ptr = ptr->get_ltree();            // point to left subtree
  194.     continue;                // And continue to search;
  195.       }
  196.     }
  197.     else {                    // Else down right subtree
  198.       if (ptr->get_rtree() == NULL)         // If at leaf node
  199.     return FALSE;                // Indicate success
  200.       else {
  201.     if (avl)                 // If an avl tree
  202.       stack1.push (Stack_Entry((CoolBinary_Node*)ptr,RIGHT)); // push on stack
  203.     parent_ptr = ptr;            // Save parent pointer
  204.     route = RIGHT;                // Save route taken
  205.     ptr = ptr->get_rtree();            // Point to right subtree
  206.     continue;                // And continue to search;
  207.       }
  208.     }
  209.   }
  210.   // The node has been removed.  Now every node in the path of the deleted
  211.   // node must be checked for possible re-balancing if this is an AVL tree
  212.   if (avl)
  213.     CoolBinary_Tree::avl_remove_balance (stack1);
  214.   return TRUE;
  215. }
  216.  
  217.  
  218.  
  219.       
  220.  
  221. // find -- Find a value in the sorted binary tree 
  222. // Input:  Reference to value to find
  223. // Output: Current position updated and TRUE if item found, FALSE otherwise
  224.  
  225. template <class Type>
  226. Boolean CoolBinary_Tree<Type>::find (const Type& value) {
  227.   for (this->reset (); this->next (); )      // For each node in the tree
  228.     if ((*this->compare)(this->value(), value) == 0) // If value found in cache
  229.       return TRUE;                // Indicate item found
  230.   return FALSE;                    // Else indicate failure
  231. }
  232.  
  233.  
  234. // operator<< -- Output a binary tree by printing it sideways where the root is
  235. //               printed at the left margin. To obtain the normal orientation,
  236. //               rotate the output 90 degrees clockwise
  237. // Input:        Reference to output stream, reference to CoolBinary_Tree<Type>
  238. // Output:       Reference to output stream
  239.  
  240. template <class Type> CoolBinary_Tree {
  241. ostream& operator<< (ostream& os, const CoolBinary_Tree<Type>& b) {
  242.   Type##_print_tree((CoolBinary_Node<Type>*)b.get_root(),os); // Print tree 
  243.   return os;                     // Return output stream
  244. }
  245. }
  246.  
  247.  
  248.  
  249. template <class Type> CoolBinary_Tree {
  250. void Type##_print_tree (const CoolBinary_Node<Type>* b, ostream& os) {
  251.   static indent = 0;                // Temporary variables
  252.   if (b != NULL) {                // If not at bottom of tree
  253.     indent += 1;                // Indent node
  254.     Type##_print_tree (b->get_rtree(),os);    // Output the right subtree
  255.     for (int i = 1; i < indent; i++)        // For each level of tree
  256.       os << "     ";                // Indent some number of spaces
  257.       os << b->get() << "\n";            // Output node data value
  258.     Type##_print_tree (b->get_ltree(),os);    // Output the left subtree
  259.     indent -= 1;                // Decrement indent level
  260.   }
  261. }}
  262.  
  263.  
  264. // operator= -- Overload the assignment operator to copy a CoolBinary_Tree object
  265. //              to another Binary Tree object
  266. // Input:       Reference to CoolBinary_Tree
  267. // Output:      Reference to CoolBinary_Tree
  268.  
  269. template <class Type>
  270. CoolBinary_Tree<Type>& CoolBinary_Tree<Type>::operator= (CoolBinary_Tree<Type>& b) {
  271.   delete this->root;                // Delete old tree nodes, virtual
  272.   this->compare = b.compare;            // Pointer to compare function
  273.   this->number_nodes = b.number_nodes;
  274.   this->current_position () = b.current_position ();
  275.   this->root = this->copy_nodes (b.get_root());
  276.   return *this;                    // Return tree reference
  277. }
  278.  
  279.  
  280. template <class Type>
  281. inline CoolBinary_Node<Type>* CoolBinary_Tree<Type>::copy_nodes(const CoolBinary_Node<Type>* bn) const{
  282.   CoolBinary_Node<Type>* new_nodes = NULL;
  283.   if (bn)
  284.     new_nodes = bn->copy_nodes(bn);
  285.   return new_nodes;
  286. }
  287.  
  288.  
  289. // balance -- Build a perfectly balanced binary tree from the existing tree
  290. //            and delete old tree and storage. This uses the private recursive
  291. //            method baltree() to construct the left and then right subtrees.
  292. // Input:     None
  293. // Output:    None
  294.  
  295. template <class Type>
  296. void CoolBinary_Tree<Type>::balance () {
  297.   CoolBinary_Node<Type>* p;                // Temporary node pointer
  298.   if (this->number_nodes != 0) {        // If there are nodes in tree
  299.     this->reset ();                // Recalculate node cache
  300.     p = this->baltree (this->number_nodes);    // Generate balanced tree
  301.     delete this->root;                // Delete old tree, virtual
  302.     this->root = p;                // Point to new balanced tree
  303.   }
  304. }
  305.  
  306. template <class Type>
  307. CoolBinary_Node<Type>* CoolBinary_Tree<Type>::baltree (long n) {
  308.   long nleft, nright;                // Number nodes in ltree,rtree
  309.   CoolBinary_Node<Type>* p;                // Temporary pointer
  310.   if (n == 0)                    // If no more nodes left
  311.     return NULL;                // Return NULL pointer
  312.   nleft = n >> 1;                // Node count for left subtree
  313.   nright = n - nleft - 1;            // Node count for right subtree
  314.   p = new CoolBinary_Node<Type> ();            // Allocate new node
  315.   p->set_ltree(this->baltree (nleft));        // Create left subtree
  316.   p->set ((this->next(), this->value()));    // Set node value
  317.   p->set_rtree(this->baltree (nright));        // Create right subtree
  318.   return p;                    // Return pointer to subtree
  319. }
  320.  
  321.  
  322. // operator== -- Compare binary trees for same values and structure
  323. // Input:        constant reference to another binary tree
  324. // Output:       TRUE/FALSE
  325.  
  326. template <class Type>
  327. Boolean CoolBinary_Tree<Type>::operator== (CoolBinary_Tree<Type>& t) {
  328.   Boolean t1, t2;
  329.   for (this->reset(), t.reset();        // Start at first node of each
  330.        (t1 = this->next()) && (t2 = t.next());) // For each node in tree
  331.     if ((*this->compare)(this->value(), t.value()) != 0) // If different value
  332.       return FALSE;                     // Trees not equal
  333.   if (t1 == FALSE)                     // If no more nodes 
  334.     if (t.next () == FALSE)                 // in either tree
  335.       return TRUE;                     // Trees are equal
  336.     else
  337.       return FALSE;
  338.   return FALSE;                         // Else not equal
  339. }
  340.  
  341. // set_compare -- Specify the comparison function to be used in logical tests
  342. //                of node data values
  343. // Input:         Pointer to a compare function
  344. // Output:        None
  345.  
  346. template <class Type>
  347. void CoolBinary_Tree<Type>::set_compare (Type##_Tree_Compare cf) {
  348.   if (cf)                    // If compare function given
  349.     this->compare = cf;                // Set pointer
  350.   else
  351.     this->compare = &Type##_default_node_compare; // Pointer to default compare
  352. }
  353.  
  354. // default_node_compare -- Default node comparison function utilizing builtin
  355. //                         less than, equal, and greater than operators
  356. // Input:                  Reference to two Type data values
  357. // Output:                 -1, 0, or 1 if less than, equal to, or greater than
  358.  
  359. template <class Type> CoolBinary_Tree {
  360.   int Type##_default_node_compare (const Type& v1, const Type& v2) {
  361.     if (v1 == v2)                // If data items equal
  362.       return 0;                    // Return zero
  363.     if (v1 < v2)                // If this less than data
  364.       return -1;                // Return negative one
  365.     return 1;                    // Else return positive one
  366.   }
  367. }
  368.  
  369.